package code.mySpecializedTraining;

import java.util.*;

/**
 * @author 26029
 * @date 2025/4/9
 * @description
 */
public class DP {

    // 1049. 最后一块石头的重量 II
    public int lastStoneWeightII(int[] stones) {
        int len = stones.length;
        int sum = Arrays.stream(stones).sum();
        int half_sum = sum / 2;
        // stones=背包物品；stones[i]=物品i的重量，half_sum=背包容量
        // 01背包：求不超过背包容量，最多能拿多重的物品
        int[][] dp = new int[len + 1][half_sum + 1]; // dp[i][j]表示前i个物品，背包容量为j，最多拿多重
        for (int i = 1; i <= len; i++) {
            int now_stone = stones[i - 1];
            for (int j = 1; j <= half_sum; j++) {
                if (j >= now_stone)
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - now_stone] + now_stone);
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }
        return sum - 2 * dp[len][half_sum];
    }

    // 494. 目标和
    public int findTargetSumWays(int[] nums, int target) {
        // pos + neg = target
        // pos - neg = sum
        // 2 * pos = target + sum
        // pos = (target + sum) / 2
        // 01背包：求选取物品重量为pos的选取方式数量（顺序无关）
        int len = nums.length;
        int sum = Arrays.stream(nums).sum();
        // 如果target + sum为奇数，不存在答案；如果pos为负，不存在答案
        if ((sum + target) % 2 == 1 || sum + target < 0)
            return 0;
        int pos = (sum + target) / 2;
        // dp[i][j]表示前i个物品组成重量为j的方案数
        int[][] dp = new int[len + 1][pos + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= len; i++) {
            int nowItem = nums[i - 1];
            for (int j = 0; j <= pos; j++) {
                if (j >= nowItem)
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nowItem];
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[len][pos];
    }

    // 474. 一和零
    public int findMaxForm(String[] strs, int m, int n) {
        // 两个维度的背包，背包大小有m和n两个维度
        // 背包物品时strs，背包大小为(m, n)
        // 01背包：求不超过背包大小，能拿的最多物品数
        int len = strs.length;
        // dp[i][j][k]表示前i个物品，背包大小为(j, k)，能拿的最多物品数
        int[][][] dp = new int[len + 1][m + 1][n + 1];
        for (int i = 1; i <= len; i++) {
            int[] num01 = get01Num(strs[i - 1]);
            int num0 = num01[0], num1 = num01[1];
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
                    if (j >= num0 && k >= num1)
                        dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - num0][k - num1] + 1);
                    else
                        dp[i][j][k] = dp[i - 1][j][k];
                }
            }
        }
        return dp[len][m][n];
    }

    private int[] get01Num(String s) {
        int[] ans = new int[2];
        int len = s.length();
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if (c == '0')
                ans[0]++;
            else if (c == '1')
                ans[1]++;
        }
        return ans;
    }

    // 279. 完全平方数
    public int numSquares(int n) {
        int start = 1;
        List<Integer> item = new ArrayList<>();
        while (start * start <= n) {
            item.add(start * start);
            start++;
        }
        int len = item.size();
        // 完全背包：求item组成重量n的最少选取数量
        // dp[i][j]表示前i个物品组成重量j的最少选取数量
        int[][] dp = new int[len + 1][n + 1];
        for (int j = 1; j <= n; j++) {
            dp[0][j] = n;
        }
        for (int i = 1; i <= len; i++) {
            int num = item.get(i - 1);
            for (int j = 1; j <= n; j++) {
                if (j >= num)
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - num] + 1);
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[len][n];
    }

    // 139. 单词拆分
    public boolean wordBreak(String s, List<String> wordDict) {
        // wordDict为物品，互不相同，s为背包大小，只不过这个背包指定了存放物品的顺序按s来
        int len = wordDict.size();
        int bagSize = s.length();
        // 完全背包：求是否可以填满背包。无重复元素.顺序相关！考虑转为爬楼梯问题！
        // dp[i]表示能否填满大小为j的背包（s的前j个字符）
        boolean[] dp = new boolean[bagSize + 1];
        dp[0] = true;
        // 爬楼梯，先遍历台阶，再遍历步数
        for (int i = 1; i <= bagSize; i++) {
            for (int j = 0; j < len; j++) {
                String word = wordDict.get(j);
                int wordLen = word.length();
                if (i >= wordLen && word.equals(s.substring(i - wordLen, i)))
                    dp[i] = dp[i] || dp[i - wordDict.get(j).length()];
            }
        }
        return dp[bagSize];
    }

    // 140. 单词拆分 II
    public List<String> wordBreak2(String s, List<String> wordDict) {
        // 回溯？
        Set<String> set = new HashSet<>();
        for (String word : wordDict)
            set.add(word);
        List<String> stringList = new ArrayList<>();
        DFS140(set, stringList, new StringBuilder(), 0, s);
        return stringList;
    }

    private void DFS140(Set<String> set, List<String> stringList, StringBuilder sb, int beginIndex, String s) {
        if (beginIndex == s.length()) {
            sb.deleteCharAt(sb.length() - 1);
            stringList.add(sb.toString());
            sb.append(" ");
            return;
        }
        if (beginIndex > s.length())
            return;
        for (int i = beginIndex; i < s.length(); i++) {
            String possibleWord = s.substring(beginIndex, i + 1);
            if (!set.contains(possibleWord))
                continue;
            sb.append(possibleWord);
            sb.append(" ");
            DFS140(set, stringList, sb, i + 1, s);
            sb.deleteCharAt(sb.length() - 1);
            sb.delete(sb.length() - possibleWord.length() - 1, sb.length());
        }
    }

    // 122. 买卖股票的最佳时机 II
    public int maxProfit2(int[] prices) {
        int len = prices.length;
        int[] have = new int[len]; // have[i]表示第i天拥有股票的最大利润
        int[] no = new int[len]; // no[i]表示第i天没有股票的最大利润
        have[0] = -prices[0];
        no[0] = 0;
        for (int i = 1; i < len; i++) {
            have[i] = Math.max(have[i - 1], no[i - 1] - prices[i]);
            no[i] = Math.max(no[i - 1], have[i - 1] + prices[i]);
        }
        return no[len - 1];
    }

    // 123. 买卖股票的最佳时机 III
    public int maxProfit3(int[] prices) {
        int len = prices.length;
        int[][] buy = new int[len][2]; // buy[i][j]表示第i天买第j次股票的最大利润
        int[][] sell = new int[len][2]; // sell[i][j]表示第i天卖第j次股票的最大利润
        buy[0][0] = -prices[0];
        sell[0][0] = 0;
        buy[0][1] = -prices[0];
        sell[0][1] = 0;
        for (int i = 1; i < len; i++) {
            buy[i][0] = Math.max(buy[i - 1][0], -prices[i]);
            sell[i][0] = Math.max(sell[i - 1][0], buy[i][0] + prices[i]);
            buy[i][1] = Math.max(buy[i - 1][1], sell[i][0] - prices[i]);
            sell[i][1] = Math.max(sell[i - 1][1], buy[i][1] + prices[i]);
        }
        return sell[len - 1][1];
    }

    // 62. 不同路径
    public int uniquePaths(int m, int n) {
        // 二维爬楼梯问题
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }

    // 63. 不同路径 II
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            if (obstacleGrid[i][0] == 1)
                break;
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            if (obstacleGrid[0][i] == 1)
                break;
            dp[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1)
                    continue;
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }

    // 416. 分割等和子集
    public boolean canPartition(int[] nums) {
        // 01背包问题,物品为nums,背包大小为sum/2,求能否刚好填满背包,顺序无关,有重复元素,不能重复使用.不能转为爬楼梯问题!
        int len = nums.length;
        int sum = Arrays.stream(nums).sum();
        if (sum % 2 == 1)
            return false;
        int size = sum / 2;
        // dp[i][j]表示前i个元素能否填满j的背包
        boolean[][] dp = new boolean[len + 1][size + 1];
        // 初始化,j=0,一定能填满
        for (int i = 0; i <= len; i++) {
            dp[i][0] = true;
        }
        for (int i = 1; i <= len; i++) {
            int num = nums[i - 1];
            for (int j = 1; j <= size; j++) {
                if (j >= num)
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - num];
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[len][size];
    }

    // 518. 零钱兑换 II
    public int change(int amount, int[] coins) {
        // 完全背包:可多次选,无重复元素,顺序无关
        int len = coins.length;
        int[][] dp = new int[len + 1][amount + 1];
        // 1 <= coins[i] <= 5000
        for (int i = 0; i <= len; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= len; i++) {
            int coin = coins[i - 1];
            for (int j = 1; j <= amount; j++) {
                if (j >= coin)
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coin];
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[len][amount];
    }

    // 377. 组合总和 Ⅳ
    public int combinationSum4(int[] nums, int target) {
        // 完全背包:可重复选,顺序相关,无重复元素→直接转化为爬楼梯问题
        int len = nums.length;
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int num : nums) {
                if (i >= num)
                    dp[i] += dp[i - num];
            }
        }
        return dp[target];
    }

    // 322. 零钱兑换
    public int coinChange(int[] coins, int amount) {
        // 完全背包:可重复选,无重复元素,顺序无关
        // 求填满背包的最少物品数量
        int len = coins.length;
        // dp[i][j]表示前i个物品填满j所需最少物品数量
        int[][] dp = new int[len + 1][amount + 1];
        for (int i = 0; i <= len; i++) {
            dp[i][0] = 0;
        }
        for (int j = 1; j <= amount; j++) {
            dp[0][j] = amount + 1;
        }
        for (int i = 1; i <= len; i++) {
            int coin = coins[i - 1];
            for (int j = 1; j <= amount; j++) {
                if (j >= coin)
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coin] + 1);
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[len][amount] == amount + 1 ? -1 : dp[len][amount];
    }

    // 309. 买卖股票的最佳时机含冷冻期
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len == 1)
            return 0;
        int[] have = new int[len];
        int[] no = new int[len];
        have[0] = -prices[0];
        no[0] = 0;
        have[1] = Math.max(have[0], -prices[1]);
        no[1] = Math.max(no[0], have[0] + prices[1]);
        for (int i = 2; i < len; i++) {
            have[i] = Math.max(have[i - 1], no[i - 2] - prices[i]);
            no[i] = Math.max(no[i - 1], have[i - 1] + prices[i]);
        }
        return no[len - 1];
    }

    // 714. 买卖股票的最佳时机含手续费
    public int maxProfit(int[] prices, int fee) {
        int len = prices.length;
        int[] have = new int[len];
        int[] no = new int[len];
        have[0] = -prices[0] - fee;
        no[0] = 0;
        for (int i = 1; i < len; i++) {
            have[i] = Math.max(have[i - 1], no[i - 1] - prices[i] - fee);
            no[i] = Math.max(no[i - 1], have[i - 1] + prices[i]);
        }
        return no[len - 1];
    }

    // 1035. 不相交的线
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        // 最长公共子序列问题
        int len1 = nums1.length, len2 = nums2.length;
        int[][] dp = new int[len1 + 1][len2 + 1];
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (nums1[i - 1] == nums2[j - 1])
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                else
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[len1][len2];
    }

    // 53. 最大子数组和
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len]; // dp[i] 表示以i结尾的子数组，最大子数组和
        dp[0] = nums[0];
        int max = dp[0];
        for (int i = 1; i < len; i++) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            max = Math.max(max, dp[i]);
        }
        return max;
    }

    // 918. 环形子数组的最大和
    public int maxSubarraySumCircular(int[] nums) {
        int total = 0, maxSum = nums[0], curMax = 0, minSum = nums[0], curMin = 0;
        for (int num : nums) {
            // 第一种情况：子数组在中间
            // [××√√×]
            curMax = Math.max(curMax + num, num);
            maxSum = Math.max(maxSum, curMax);
            // 第二种情况：子数组一部分在尾部，一部分在下一圈的首部
            // [××××√][√√×××] <-> [√××√√] = [MaxSub1 | MinSub | MaxSub2]
            // 求最小子数组和，然后用total减去它
            curMin = Math.min(curMin + num, num);
            minSum = Math.min(minSum, curMin);
            // 单纯求出所有元素之和
            total += num;
        }
        return maxSum > 0 ? Math.max(maxSum, total - minSum) : maxSum;
    }

    // 392. 判断子序列
    public boolean isSubsequence(String s, String t) {
        // 传统做法,俩指针就行,但是主要考虑大量输入s的情况
        // 两个字符串都只由小写字符组成
        int sLen = s.length(), tLen = t.length();
        // help[i][j]表示t中的第i个字符的下一个j字符在t中的下标
        int[][] help = new int[tLen + 1][26];
        for (int j = 0; j < 26; j++) {
            help[tLen][j] = 26; // 代表没有下一个了
        }
        for (int i = tLen - 1; i >= 0; i--) {
            for (int j = 0; j < 26; j++) {
                char nextC = (char) (j + 'a');
                // 如果它上一个就是,则赋值
                if (nextC == t.charAt(i))
                    help[i][j] = i + 1;
                else
                    help[i][j] = help[i + 1][j];
            }
        }
        // 对于大量的输入s,每个s只需根据help查找即可
        int count = 0;
        int nextPos = 0;
        for (int i = 0; i < sLen; i++) {
            char sC = s.charAt(i);
            int tempPos = help[nextPos][sC - 'a'];
            if (tempPos == 26)
                return false;
            nextPos = tempPos;
            count++;
        }
        return count == sLen;
    }

    // 115. 不同的子序列
    public int numDistinct(String s, String t) {
        int sLen = s.length(), tLen = t.length();
        // dp[i][j]表示s的前i个组成t的前j个的方案
        int[][] dp = new int[sLen + 1][tLen + 1];
        for (int i = 0; i <= sLen; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= sLen; i++) {
            char sChar = s.charAt(i - 1);
            for (int j = 1; j <= tLen; j++) {
                char tChar = t.charAt(j - 1);
                if (sChar == tChar)
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[sLen][tLen];
    }

    // 583. 两个字符串的删除操作
    public int minDistance(String word1, String word2) {
        // ans = len1 + len2 - 2 * 最长公共子序列长度
        int len1 = word1.length(), len2 = word2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        for (int i = 1; i <= len1; i++) {
            char c1 = word1.charAt(i - 1);
            for (int j = 1; j <= len2; j++) {
                char c2 = word2.charAt(j - 1);
                if (c1 == c2)
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return len1 + len2 - 2 * dp[len1][len2];
    }

    // 72. 编辑距离
    public int minDistance_(String word1, String word2) {
        int len1 = word1.length(), len2 = word2.length();
        // dp[i][j]表示word1前i和word2前j的距离(最少转换操作次数)
        int[][] dp = new int[len1 + 1][len2 + 1];
        for (int i = 0; i <= len1; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= len2; j++) {
            dp[0][j] = j;
        }
        for (int i = 1; i <= len1; i++) {
            char c1 = word1.charAt(i - 1);
            for (int j = 1; j <= len2; j++) {
                char c2 = word2.charAt(j - 1);
                // 如果末尾两元素相同
                if (c1 == c2)
                    // 可以选择替换,删除,新增
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(1 + dp[i][j - 1], 1 + dp[i - 1][j]));
                else
                    dp[i][j] = Math.min(1 + dp[i - 1][j - 1], Math.min(1 + dp[i][j - 1], 1 + dp[i - 1][j]));
            }
        }
        return dp[len1][len2];
    }

    // 647. 回文子串
    public int countSubstrings(String s) {
        // 回文子串,二维dp斜着遍历
        int len = s.length();
        // dp[i][j]表示s[i]-s[j]的回文子串的个数
        int[][] dp = new int[len][len];
        // ok[i][j]表示s[i]-s[j]是不是回文子串
        boolean[][] ok = new boolean[len][len];
        // gap = 0
        for (int i = 0; i < len; i++) {
            dp[i][i] = 1;
            ok[i][i] = true;
        }
        // gap = 1;
        for (int i = 0; i < len - 1; i++) {
            ok[i][i + 1] = s.charAt(i) == s.charAt(i + 1);
            dp[i][i + 1] = ok[i][i + 1] ? 3 : 2;
        }
        // 2 <= gap <= len - 1
        for (int gap = 2; gap <= len - 1; gap++) {
            for (int start = 0; start <= len - 1 - gap; start++) {
                int end = start + gap;
                ok[start][end] = s.charAt(start) == s.charAt(end) && ok[start + 1][end - 1];
                dp[start][end] = dp[start][end - 1] + dp[start + 1][end] - dp[start + 1][end - 1];
                dp[start][end] += ok[start][end] ? 1 : 0;
            }
        }
        return dp[0][len - 1];
    }

    // 516. 最长回文子序列
    public int longestPalindromeSubseq(String s) {
        int len = s.length();
        // dp[i][j]表示从i到j的最长回文子序列
        int[][] dp = new int[len][len];
        // gap = 0
        for (int i = 0; i < len; i++) {
            dp[i][i] = 1;
        }
        // gap = 1
        for (int i = 0; i < len - 1; i++) {
            dp[i][i + 1] = s.charAt(i) == s.charAt(i + 1) ? 2 : 1;
        }
        // 2 <= gap <= len - 1
        for (int gap = 2; gap <= len - 1; gap++) {
            for (int start = 0; start <= len - 1 - gap; start++) {
                int end = start + gap;
                if (s.charAt(start) == s.charAt(end))
                    dp[start][end] = 2 + dp[start + 1][end - 1];
                else
                    dp[start][end] = Math.max(dp[start + 1][end], dp[start][end - 1]);
            }
        }
        return dp[0][len - 1];
    }

    // 300. 最长递增子序列 DP
    public int lengthOfLIS(int[] nums) {
        // 常规dp,O(n^2),和暴力一个复杂度,不如->贪心+二分
        int len = nums.length;
        int[] dp = new int[len];
        dp[0] = 1;
        int ans = dp[0];
        for (int i = 1; i < len; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i])
                    dp[i] = Math.max(dp[i], 1 + dp[j]);
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }

    // 300. 最长递增子序列 Greedy
    public int lengthOfLIS_greedy(int[] nums) {
        // tails[k]表示长度为k+1的递增子序列的末尾元素,贪心在这个末尾元素要找最小的
        int len = nums.length;
        int[] tails = new int[len];
        int maxLen = 0;
        // 如果当前元素比之前的小,则替换掉之前的,替换位置就是递增子序列长度,他作为这个长度的末尾元素
        for (int num : nums) {
            // 二分查找插入位置
            int left = 0, right = maxLen;
            int insertPos = right;
            while (left <= right) {
                int mid = (right - left) / 2 + left;
                if (tails[mid] < num)
                    left = mid + 1;
                else if (num <= tails[mid]) {
                    right = mid - 1;
                    insertPos = mid;
                }
            }
            tails[insertPos] = num;
            if (insertPos == maxLen)
                maxLen++;
        }
        return maxLen;
    }

    // 674. 最长连续递增序列
    public int findLengthOfLCIS(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len]; // dp[i]表示以元素i结尾的最长连续递增子序列长度
        dp[0] = 1;
        int ans = dp[0];
        for (int i = 1; i < len; i++) {
            if (nums[i] > nums[i - 1])
                dp[i] = dp[i - 1] + 1;
            else
                dp[i] = 1;
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }

    // 718. 最长重复子数组
    public int findLength(int[] nums1, int[] nums2) {
        int len1 = nums1.length, len2 = nums2.length;
        int[][] dp = new int[len1 + 1][len2 + 1]; // dp[i][j]表示nums1以i结尾和nums2以j结尾的最长重复数组(连续的)
        int ans = 0;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (nums1[i - 1] == nums2[j - 1])
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                else
                    dp[i][j] = 0;
                ans = Math.max(ans, dp[i][j]);
            }
        }
        return ans;
    }

    // 1143. 最长公共子序列
    public int longestCommonSubsequence(String text1, String text2) {
        int len1 = text1.length(), len2 = text2.length();
        int[][] dp = new int[len1 + 1][len2 + 1]; // dp[i][j]表示nums1前i个和nums2前j个的最长重复数组
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1))
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                else
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[len1][len2];
    }

    // 132. 分割回文串 II
    public int minCut(String s) {
        int n = s.length();
        // 预处理 s 获得二维数组 isHuiwen[i][j] 表示所有子串 s[i-j] 是否为回文串的信息
        boolean[][] isHuiwen = new boolean[n][n];
        for (int i = 0; i < n; i++)
            isHuiwen[i][i] = true;
        for (int i = 0; i < n - 1; i++)
            isHuiwen[i][i + 1] = s.charAt(i) == s.charAt(i + 1);
        for (int len = 3; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                isHuiwen[i][j] = s.charAt(i) == s.charAt(j) && isHuiwen[i + 1][j - 1];
            }
        }
        // dp[i] 表示 s[0-i] 子串的最少分割次数
        // 当 isHuiwen[j+1][i]=true 时 dp[i]=min(dp[j])+1
        int[] dp = new int[n];
        dp[0] = 0;
        for (int i = 1; i < n; i++) {
            if (isHuiwen[0][i]) {
                dp[i] = 0;
                continue;
            }
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < i; j++) {
                if (isHuiwen[j + 1][i])
                    min = Math.min(min, dp[j] + 1);
            }
            dp[i] = min;
        }
        return dp[n - 1];
    }

    // 174. 地下城游戏（不满足无后效性）
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length, n = dungeon[0].length;
        int[][] dp = new int[m + 1][n + 1]; // dp[i][j] 表示从 dungeon[i - 1][j - 1] 到达终点时需要的最少 hp
        for (int i = 0; i <= m; i++)
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        dp[m][n - 1] = dp[m - 1][n] = 1;
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int min = Math.min(dp[i + 1][j], dp[i][j + 1]);
                if (dungeon[i][j] >= 0) {
                    dp[i][j] = Math.max(min - dungeon[i][j], 1);
                } else {
                    dp[i][j] = min - dungeon[i][j];
                }
            }
        }
        return dp[0][0];
    }

    // 2140. 解决智力问题（不满足无后效性）
    public long mostPoints(int[][] questions) {
        // 当前选择会影响接下来的选择，不满足无后效性，试着从后往前遍历
        int n = questions.length; // 1 <= questions.length <= 105
        long[] dp = new long[n]; // dp[i] 表示考虑问题i到n，最多能拿多少分
        dp[n - 1] = questions[n - 1][0];
        for (int i = n - 2; i >= 0; i--) {
            if (i + questions[i][1] + 1 < n)
                dp[i] = Math.max(dp[i + 1], questions[i][0] + dp[i + questions[i][1] + 1]);
            else
                dp[i] = Math.max(dp[i + 1], questions[i][0]);
        }
        return dp[0];
    }

    // 264. 丑数 II
    public int nthUglyNumber(int n) {
        // 第n个丑数为第1~(n-1)中的某个丑数x2、x3、x5得到
        PriorityQueue<Long> pq = new PriorityQueue<>(); // 存放所有之后会出现的丑数
        Set<Long> set = new HashSet<>(); // 避免重复放入pq
        pq.offer(1L);
        set.add(1L);
        int count = 0;
        while (!pq.isEmpty()) {
            long now = pq.poll();
            count++;
            if (count == n) {
                return (int) now;
            }
            long now2 = now * 2, now3 = now * 3, now5 = now * 5;
            if (!set.contains(now2)) {
                pq.offer(now2);
                set.add(now2);
            }
            if (!set.contains(now3)) {
                pq.offer(now3);
                set.add(now3);
            }
            if (!set.contains(now5)) {
                pq.offer(now5);
                set.add(now5);
            }
        }
        return -1;
    }

    public int nthUglyNumber_DP(int n) {
        int[] dp = new int[n];
        dp[0] = 1;
        int index2 = 0, index3 = 0, index5 = 0;
        for (int i = 1; i < n; i++) {
            dp[i] = Math.min(Math.min(dp[index2] * 2, dp[index3] * 3), dp[index5] * 5);
            if (dp[i] == dp[index2] * 2)
                index2++;
            if (dp[i] == dp[index3] * 3)
                index3++;
            if (dp[i] == dp[index5] * 5)
                index5++;
        }
        return dp[n - 1];
    }

    // 313. 超级丑数
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] dp = new int[n];
        int len = primes.length;
        int[] indexes = new int[len];
        int[] targets = new int[len];
        for (int i = 0; i < len; i++) {
            targets[i] = primes[i];
        }
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            // 找最小值
            for (int j = 0; j < len; j++) {
                if (targets[j] < 0)
                    targets[j] = Integer.MAX_VALUE;
            }
            int min = Arrays.stream(targets).min().getAsInt();
            dp[i] = min;
            // 在这里更新index和对应的target，所有target==min的index都要更新，因为可能有重复的
            for (int j = 0; j < len; j++) {
                if (targets[j] == min) {
                    indexes[j]++;
                    targets[j] = primes[j] * dp[indexes[j]];
                }
            }
        }
        return dp[n - 1];
    }

    // 343. 整数拆分
    public int integerBreak(int n) {
        int max = 0;
        for (int i = 2; i <= n; i++) {
            int num = n / i;
            int yu = n % i;
            int pure = i - yu;
            int pureAns = (int) Math.pow(num, pure);
            int yuAns = (int) Math.pow(num + 1, yu);
            max = Math.max(max, pureAns * yuAns);
        }
        return max;
    }

    // 357. 统计各位数字都不同的数字个数
    public int countNumbersWithUniqueDigits(int n) {
        // n=0  0           1               1
        // n=1  1-9         9               10
        // n=2  10-99       81=9*9          91
        // n=3  100-999     648=9*9*8       739
        // n=4  1000-9999   4536=9*9*8*7    5275
        int[] dp = new int[n + 1]; // dp[i]表示到i位数的所有数字中（0算作0位数），有多少个合理的数 dp[i] = 9 * (9 * 8 * 7 * ... 一共i-1个)
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            int base = 9;
            int a = 1;
            int minus = 9;
            for (int j = 0; j < i - 1; j++) {
                a *= minus;
                minus--;
            }
            dp[i] = dp[i - 1] + a * base;
        }
        return dp[n];
    }

    // 368. 最大整除子集
    public List<Integer> largestDivisibleSubset(int[] nums) {
        int len = nums.length;
        // 排序
        Arrays.sort(nums);
        // 类似于：最长递增子序列。这个题也是求一个“子序列”，要求后一个能整除前一个
        int[] dp = new int[len]; // dp[i] 表示以 nums[i] 结尾的最大整除子集（子序列）的长度
        int[] prev = new int[len]; // prev[i] 表示 nums[i] 的前一个子集中的元素位置
        Arrays.fill(prev, -1);
        Arrays.fill(dp, 1);
        int totalMax = 1, totalMaxPos = 0;
        for (int i = 1; i < len; i++) {
            int max = 1;
            int prevPos = -1;
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0) {
                    if (dp[j] + 1 > max) {
                        max = dp[j] + 1;
                        prevPos = j;
                    }
                }
            }
            dp[i] = max;
            prev[i] = prevPos;
            if (max > totalMax) {
                totalMax = max;
                totalMaxPos = i;
            }
        }
        // 由于需要返回的是具体的子集（序列），而非长度，所以用 prev 求得
        List<Integer> list = new ArrayList<>();
        list.add(nums[totalMaxPos]);
        while (prev[totalMaxPos] != -1) {
            totalMaxPos = prev[totalMaxPos];
            list.add(nums[totalMaxPos]);
        }
        return list;
    }

    // 396. 旋转函数
    public int maxRotateFunction(int[] nums) {
        // 下一个值取决于上一个值减去(n - 1)倍的最右值再加上全部剩余的值
        int n = nums.length;
        int sum = Arrays.stream(nums).sum();
        int[] f = new int[n]; // f[i] = f[i - 1] - (len - 1) * nums[len - (i - 1) - 1] + (len - 1) * (sum - nums[len - (i - 1) - 1])
        for (int i = 0; i < n; i++) {
            f[0] += nums[i] * i;
        }
        for (int i = 1; i < n; i++) {
            // f[i] = f[i - 1] - (n - 1) * nums[n - (i - 1) - 1] + (sum - nums[n - (i - 1) - 1]);
            f[i] = f[i - 1] - n * nums[n - (i - 1) - 1] + sum;
        }
        return Arrays.stream(f).max().getAsInt();
    }

    // 397. 整数替换
    public int integerReplacement_dp(int n) {
        // 这道题由于 1 <= n <= 2^31 - 1 不能用开大小为n的dp数组做，但还是放上方法
        //  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
        //  0  1  2  2  3  3  4  3  4  4  5  4  5  5  5  4
        int[] dp = new int[n + 2]; // dp[i] 表示从数字 i 变为 1 的最小替换次数，注意一定要n+2的数组，因为如果n是奇数，那么还是需要n+1来判断的
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[1] = 0;
        // 因为奇数涉及到n+1和n-1，而这些又都是偶数，所以先遍历偶数
        // 偶数不能一次性遍历完，因为类似6这样的偶数取决于3，而3是奇数
        for (int i = 2; i <= n + 1; i *= 2) {
            dp[i] = dp[i / 2] + 1;
        }
        // 1 2 4 8 16 32...已经有值了，现在找奇数，一边找奇数，一边把除以2等于奇数的偶数也补全
        for (int i = 3; i <= n; i += 2) {
            dp[i] = 1 + Math.min(dp[i - 1], dp[i + 1]);
            int thinkAbout2 = i * 2;
            while (thinkAbout2 <= n) {
                dp[thinkAbout2] = dp[thinkAbout2 / 2] + 1;
                thinkAbout2 *= 2;
            }
        }
        return dp[n];
    }


    public int integerReplacement_dfs(int n) {
        // 回溯
        return dfs397((long) n, 0);
    }

    private int dfs397(Long n, int times) {
        if (n == 1) {
            return times;
        }
        if (n % 2 == 0) {
            return dfs397(n / 2, times + 1);
        } else {
            int plus = dfs397(n + 1, times + 1);
            int minus = dfs397(n - 1, times + 1);
            return Math.min(plus, minus);
        }
    }

    // 413. 等差数列划分
    public int numberOfArithmeticSlices(int[] nums) {
        // 记录当前的差值和长度
        int n = nums.length;
        if (n < 2)
            return 0;
        int ans = 0;
        int diff = nums[1] - nums[0];
        int len = 2;
        for (int i = 2; i < n; i++) {
            if (nums[i] - nums[i - 1] == diff) {
                len++;
                ans += len - 2;
            } else {
                diff = nums[i] - nums[i - 1];
                len = 2;
            }
        }
        return ans;
    }

    // 526. 优美的排列（还有回溯解法）
    public int countArrangement(int n) {
        int[] dp = new int[1 << n]; // 状态 000...0 - 111...1
        dp[0] = 1;
        for (int mask = 1; mask < (1 << n); mask++) {
            int num = Integer.bitCount(mask); // 当前mask状态选取的数字个数，也是去除一个数字后要放入的位置
            for (int i = 0; i < n; i++) { // 遍历所有选取的数字 i + 1
                if ((mask & (1 << i)) == 0) // 只遍历mask选择到的数字
                    continue;
                if (num % (i + 1) == 0 || (i + 1) % num == 0) // 如果这个数字可以被插入到排列的第num个位置
                    dp[mask] += dp[mask ^ (1 << i)];
            }
        }
        return dp[(1 << n) - 1];
    }

    // 542. 01 矩阵
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] newMat = new int[m][n];
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(newMat[i], Integer.MAX_VALUE);
        }
        // 先遍历所有的0，把新的数组对应位置设为1 再把这些0相连的1加入队列
        Deque<int[]> queue = new ArrayDeque<>();
        int[][] dirs = new int[][]{{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (visited[i][j] || mat[i][j] == 1)
                    continue;
                visited[i][j] = true;
                newMat[i][j] = 0;
                // 环顾四周
                for (int k = 0; k < 4; k++) {
                    int find1x = i + dirs[k][0];
                    int find1y = j + dirs[k][1];
                    if (find1x >= 0 && find1x < m && find1y >= 0 && find1y < n && !visited[find1x][find1y] && mat[find1x][find1y] == 1) {
                        visited[find1x][find1y] = true;
                        queue.offer(new int[]{find1x, find1y, 0});
                    }
                }
            }
        }
        // BFS遍历所有加入队列的1，并再把相连的加入队列
        while (!queue.isEmpty()) {
            int[] now = queue.poll();
            int nowX = now[0], nowY = now[1], dist = now[2];
            newMat[nowX][nowY] = Math.min(dist + 1, newMat[nowX][nowY]);
            // 环顾四周
            for (int k = 0; k < 4; k++) {
                int find1x = nowX + dirs[k][0];
                int find1y = nowY + dirs[k][1];
                if (find1x >= 0 && find1x < m && find1y >= 0 && find1y < n && !visited[find1x][find1y] && mat[find1x][find1y] == 1) {
                    visited[find1x][find1y] = true;
                    queue.offer(new int[]{find1x, find1y, newMat[nowX][nowY]});
                }
            }
        }

        return newMat;
    }

    // 552. 学生出勤记录 II
    public int checkRecord(int n) {
        // 背包问题？
        // 物品是三种情况，背包大小是n，顺序相关，可重复选，无重复值。求选取的情况总数。
        // dp[i][j][k] 表示前i天，有j次缺勤，已经连续k次迟到的情况总数
        int mod = 1000000007;
        int[][][] dp = new int[n][2][3];
        dp[0][0][0] = 1; // P
        dp[0][1][0] = 1; // A
        dp[0][0][1] = 1; // L
        for (int i = 1; i < n; i++) {
            // 如果这天是P，前一天是什么都行
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 3; k++) {
                    dp[i][j][0] = (dp[i][j][0] + dp[i - 1][j][k]) % mod;
                }
            }
            // 如果这天是A，找之前没有A的情况
            for (int k = 0; k < 3; k++) {
                dp[i][1][0] = (dp[i][1][0] + dp[i - 1][0][k]) % mod;
            }
            // 如果这天是L，找之前连续迟到天数-1的情况
            for (int j = 0; j < 2; j++) {
                for (int k = 1; k < 3; k++) {
                    dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k - 1]) % mod;
                }
            }
        }
        int sum = 0;
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 3; j++) {
                sum = (sum + dp[n - 1][i][j]) % 1000000007;
            }
        }
        return sum;
    }

    // 464. 我能赢吗
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        // 如果所有数字加起来连desiredTotal都不到，就不能赢
        if ((maxChoosableInteger + 1) * maxChoosableInteger / 2 < desiredTotal)
            return false;
        // 注意到 1 <= maxChoosableInteger <= 20 可以使用状态压缩
        // 假如maxChoosableInteger=10，状态可以为(0000000101)表示已经选择了1和3的情况
        Map<Integer, Boolean> map = new HashMap<>(); // key是状态，value代表这个状态能不能赢
        // 用DFS+记忆化（记忆的是压缩的状态）
        return canIWinDFS(maxChoosableInteger, desiredTotal, 0, 0, map);
    }

    private boolean canIWinDFS(int maxChoosableInteger, int desiredTotal, int sum, int status, Map<Integer, Boolean> map) {
        if (map.containsKey(status))
            return map.get(status);
        for (int i = 1; i <= maxChoosableInteger; i++) {
            // 如果当前数字已经在状态里了，忽略
            if (((1 << (i - 1)) & status) != 0)
                continue;
            // 如果加上这个数就可以赢了，直接返回
            if (sum + i >= desiredTotal) {
                map.put(status, true);
                return true;
            }
            // 如果加上这个数也不够，那么DFS递归，注意，进入递归则是另一个人选择了，如果另一个人不能赢，自己才能赢，所以是相反的答案
            boolean canWin = !canIWinDFS(maxChoosableInteger, desiredTotal, sum + i, status | (1 << (i - 1)), map);
            if (canWin) {
                map.put(status, canWin);
                return true;
            }
        }
        map.put(status, false);
        return false;
    }

    // 467. 环绕字符串中唯一的子字符串
    public int findSubstringInWraproundString(String s) {
        // 这个也算dp？
        int len = s.length();
        int[] map = new int[26];
        int conNum = 1;
        char c = s.charAt(0);
        map[c - 'a'] = 1;
        char prev = c;
        for (int i = 1; i < len; i++) {
            // 如果连续，更新；如果不连续，重置
            c = s.charAt(i);
            if (c - prev == 1 || c == 'a' && prev == 'z') {
                conNum++;
                map[c - 'a'] = Math.max(map[c - 'a'], conNum);
            } else {
                conNum = 1;
                map[c - 'a'] = Math.max(1, map[c - 'a']);
            }
            prev = c;
        }
        return Arrays.stream(map).sum();
    }

    // 473. 火柴拼正方形（状态压缩DP）
    public boolean makesquare(int[] matchsticks) {
        // 先判断如果火柴不合适，返回
        int sum = Arrays.stream(matchsticks).sum();
        if (sum % 4 != 0) return false;
        // 设置二进制状态，0代表没选这个火柴，1代表选这个火柴，dp[status]表示状态status当前未拼完的边的长度
        int statusNum = 1 << matchsticks.length; // 1 <= matchsticks.length <= 15
        int len = matchsticks.length;
        int[] dp = new int[statusNum];
        dp[0] = 0;
        int neededLen = sum / 4;
        for (int status = 1; status < statusNum; status++) {
            // 对于每个状态，找这个状态去除火柴m的状态，如果可以转化，则更新dp
            dp[status] = -1;
            for (int m = 0; m < len; m++) {
                // 确保状态status包含火柴m
                if (((1 << m) & status) == 0)
                    continue;
                int statusWithoutM = status & ~(1 << m);
                if (dp[statusWithoutM] >= 0 && dp[statusWithoutM] + matchsticks[m] <= neededLen) {
                    dp[status] = dp[statusWithoutM] + matchsticks[m];
                    if (dp[status] == neededLen)
                        dp[status] = 0;
                    break;
                }
            }
        }
        return dp[statusNum - 1] == 0;
    }

    // 486. 预测赢家
    public boolean predictTheWinner(int[] nums) {
        int len = nums.length;
        int[][] dp = new int[len][len];
        // dp[i][j]表示nums从i到j的子数组中，可以净挣对手多少分
        for (int i = 0; i < len; i++) {
            dp[i][i] = nums[i];
        }
        for (int i = 0; i < len - 1; i++) {
            dp[i][i + 1] = Math.abs(nums[i + 1] - nums[i]);
        }
        for (int step = 2; step < len; step++) {
            for (int i = 0; i < len - step; i++) {
                int j = i + step;
                // 想在dp[i][j]净挣对手最多，有两种决策：选择nums[i]，同时让对手在dp[i+1][j]中净挣自己；选择nums[j]，同时让对手在dp[i][j - 1]中净挣自己
                dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
            }
        }
        return dp[0][len - 1] >= 0;
    }

    public boolean predictTheWinner_recursion(int[] nums) {
        return predictTheWinner_r(nums, 0, nums.length - 1) >= 0;
    }

    private int predictTheWinner_r(int[] nums, int left, int right) {
        if (left > right)
            return 0;
        int selectLeft = nums[left] - predictTheWinner_r(nums, left + 1, right);
        int selectRight = nums[right] - predictTheWinner_r(nums, left, right - 1);
        return Math.max(selectRight, selectLeft);
    }

    // 576. 出界的路径数
    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        // dfs记忆化搜索解法，还可以dp解法
        int[][][] mem = new int[m][n][maxMove]; // -1 代表没有
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < maxMove; k++) {
                    mem[i][j][k] = -1;
                }
            }
        }
        return findPaths_dfs(m, n, maxMove, startRow, startColumn, mem);
    }

    private int findPaths_dfs(int m, int n, int maxMove, int startRow, int startColumn, int[][][] mem) {
        boolean inRange = startRow >= 0 && startRow < m && startColumn >= 0 && startColumn < n;
        // 如果没超出范围，但是步数到了，说明这条路走不通，返回0
        if (maxMove == 0 && inRange)
            return 0;
        // 如果当前超出范围了，且maxMove>=0，说明可以出来
        if (maxMove >= 0 && !inRange) {
            return 1;
        }
        // 如果当前已经在记忆化搜索范围内了，直接返回
        if (mem[startRow][startColumn][maxMove - 1] != -1)
            return mem[startRow][startColumn][maxMove - 1];
        // 如果他出不去，返回0
        if (Math.min(Math.min(startRow + 1, m - startRow), Math.min(startColumn + 1, n - startColumn)) > maxMove)
            return 0;
        int allMoves = 0;
        allMoves = (allMoves + findPaths_dfs(m, n, maxMove - 1, startRow - 1, startColumn, mem)) % 1000000007;
        allMoves = (allMoves + findPaths_dfs(m, n, maxMove - 1, startRow + 1, startColumn, mem)) % 1000000007;
        allMoves = (allMoves + findPaths_dfs(m, n, maxMove - 1, startRow, startColumn - 1, mem)) % 1000000007;
        allMoves = (allMoves + findPaths_dfs(m, n, maxMove - 1, startRow, startColumn + 1, mem)) % 1000000007;
        mem[startRow][startColumn][maxMove - 1] = allMoves;
        return allMoves;
    }

    public int findPaths_dp(int m, int n, int maxMove, int startRow, int startColumn) {
        if (maxMove == 0)
            return 0;
        int[][][] dp = new int[maxMove][m][n]; // dp[move][i][j]表示使用move+1步从ij位置走出去的所有情况数
        int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        // 初始化
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int[] dir : dirs) {
                    int x = i + dir[0], y = j + dir[1];
                    if (x < 0 || x >= m || y < 0 || y >= n)
                        dp[0][i][j]++;
                }
            }
        }
        // dp
        for (int move = 1; move < maxMove; move++) {
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    // dp[move][i][j]=dp[move-1][四个方向][四个方向]
                    int add = 0;
                    for (int[] dir : dirs) {
                        int x = i + dir[0], y = j + dir[1];
                        if (!(x >= 0 && x < m && y >= 0 && y < n))
                            continue;
                        add = (add + dp[move - 1][x][y]) % 1000000007;
                    }
                    dp[move][i][j] = add;
                }
            }
        }
        int ans = 0;
        for (int move = 0; move < maxMove; move++) {
            ans = (ans + dp[move][startRow][startColumn]) % 1000000007;
        }
        return ans;
    }

    // 638. 大礼包
    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        // 优化二：去掉比单买还不合算的礼包
        List<List<Integer>> filtered = new ArrayList<>();
        for (List<Integer> s : special) {
            int singleCount = 0;
            for (int j = 0; j < price.size(); j++) {
                singleCount += price.get(j) * s.get(j);
            }
            if (singleCount < s.get(price.size()))
                continue;
            filtered.add(s);
        }
        special = filtered;
        // 先把单买也搞成礼包
        for (int i = 0; i < price.size(); i++) {
            List<Integer> list = new ArrayList<>();
            for (int j = 0; j < price.size(); j++) {
                list.add(j == i ? 1 : 0);
            }
            list.add(price.get(i));
            special.add(list);
        }
        // 优化一：回溯+记忆化：记忆满足当前needs下的最小花销，由于 0 <= needs[i] <= 10 ，故使用base11编码
        Map<Integer, Integer> map = new HashMap<>();
        int[] need = new int[needs.size()];
        for (int i = 0; i < needs.size(); i++) {
            need[i] = needs.get(i);
        }
        return shopDFS(special, need, map);
    }

    private int shopDFS(List<List<Integer>> special, int[] needs, Map<Integer, Integer> map) {
        int status = getNeedsStatus(needs);
        if (status == 0)
            return 0;
        if (map.containsKey(status))
            return map.get(status);
        int min = Integer.MAX_VALUE;
        for (List<Integer> s : special) {
            // 判断当前needs能不能拿这个礼包
            boolean flag = true;
            for (int i = 0; i < needs.length; i++) {
                if (needs[i] < s.get(i)) {
                    flag = false;
                    break;
                }
            }
            if (!flag) continue;
            // 拿上这个礼包，dfs
            for (int i = 0; i < needs.length; i++)
                needs[i] -= s.get(i);
            int offerCost = s.get(s.size() - 1);
            int nextCost = shopDFS(special, needs, map);
            if (nextCost != Integer.MAX_VALUE) {
                min = Math.min(min, offerCost + nextCost);
            }
            for (int i = 0; i < needs.length; i++)
                needs[i] += s.get(i);
        }
        map.put(status, min);
        return min;
    }

    private int getNeedsStatus(int[] needs) {
        int status = 0;
        for (Integer need : needs) {
            status = status * 11 + need;
        }
        return status;
    }

    public static void main(String[] args) {
        DP d = new DP();
        List<Integer> price = new ArrayList<>();
        price.add(0);
        price.add(0);
        price.add(0);
        List<List<Integer>> special = new ArrayList<>();
        special.add(new ArrayList<>());
        special.add(new ArrayList<>());
        special.get(0).add(1);
        special.get(0).add(1);
        special.get(0).add(0);
        special.get(0).add(4);
        special.get(1).add(2);
        special.get(1).add(2);
        special.get(1).add(1);
        special.get(1).add(9);
        List<Integer> needs = new ArrayList<>();
        needs.add(2);
        needs.add(2);
        needs.add(1);
        System.out.println(d.shoppingOffers(price, special, needs));
    }
}
